#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

class Solution {
private:
    inline static bool cmp(std::pair<const int, int>& m, std::pair<const int, int>& n)
    {
        return m.second > n.second;
    }
public:
    std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
        //统计元素出现的次数
        std::unordered_map<int, int> map;
        for(auto& key : nums)
        {
            map[key]++;
        }
        
        //小堆
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(&cmp)> heap(cmp);
        for(auto &kv : map)
        {
            if(heap.size() == k)
            {
                if(kv.second > heap.top().second)
                {
                    heap.pop();
                    heap.push(kv);
                }
            }
            else
            {
                heap.push(kv);
            }
        }

        std::vector<int> ret;
        while(!heap.empty())
        {
            ret.push_back(heap.top().first);
            heap.pop();
        }
        return ret;
    }
};

//对于kv是pair<const int, int>类型的参数，可以插入到int，int类型的pair上，
//是因为编译器的隐式类型转化，在不违反const参数不能被修改的原则时，可以进行把const转换为非const类型